package cn.willbj.brief.hootl.sort.demo;

import java.util.Arrays;

public class Demo01 {
	public static void main(String[] args) {
		// int[] arr = {8, 7, 10, 9, 1, 6, 2};
		int[] arr = {8, 7, 9, 1, 6};
		
		int[] qsort = Demo01.qsort(arr);
		System.out.println(Arrays.toString(qsort));
	}
	
	public static int[] qsort(int[] arr) {
		int[] copyOf = Arrays.copyOf(arr, arr.length);
		sortbiz(copyOf,0,copyOf.length-1);
		return copyOf;
	}
	

	private static void sortbiz(int[] copyOf, int left, int right) {
		if (left >= right) {
			return;
		}
		int partition = partition(copyOf, left, right);
		sortbiz(copyOf, left, partition-1);
		sortbiz(copyOf, partition+1, right);
	}

	public static int partition(int[] copyOf, int left, int right){
		int partition = left;
		int index = partition + 1;
		for (int i = index; i <= right; i++) {
			if (copyOf[i] < copyOf[partition]) {
				swap(copyOf,index,i);
				index++;
			}
		}
		swap(copyOf, index - 1, partition);
		return index-1;
	}
	
	public static void swap(int[] copyOf, int index, int i) {
		if (index == i) {
			return;
		}
		int temp = copyOf[i];
		copyOf[i] = copyOf[index];
		copyOf[index] = temp;
	}
	
}
